package games.checkers;

import java.util.ArrayList;

/**
 * Class to generate all possible paths for a checkers chip on a board.
 * @author chris
 *
 */
public class chipPath 
{
	public static final int start = 0; // path start
	public static final int cell = 1;  // empty cell that the chip will occupy - not the end
	public static final int jumpLeft = 2;  // jump over this tile - it has a chip on it
	public static final int jumpRight = 3;  // jump over this tile - it has a chip on it
	public static final int end = 4;   // ending place for the chip

	//private byte player;
	private chipManager manager;
	private checkersBoard board;
	private byte player;
	private int [] boardArray;
	private ArrayList<ArrayList<pathNode>> allPaths;
	
	public class pathNode {
		public int tile;
		public int action;
		
		public pathNode(int t, int a)
		{
			tile = t;
			action = a;
		}
	}
	
	/**
	 * Constructor
	 * @param s
	 * @param b
	 * @param c
	 */
	public chipPath(int t, int [] a, checkersBoard b, chipManager c)
	{
		boardArray = a;
		board = b;
		manager = c;
		allPaths = new ArrayList<ArrayList<pathNode>>();
		ArrayList<pathNode> path = new ArrayList<pathNode>();
		path.add(new pathNode(t,start));
		allPaths.add(path);
		
		//if the starting tile is not on the board, just return
		if (t == -1)
		{
			path.add(new pathNode(t,end));
			return;
		}
		
		if (boardArray[t] > 0) player = 1; else player = -1;
		
		//iterate the paths
		int d = 0;
		boolean isKing = false;
		if ((boardArray[t] == -4) || (boardArray[t] == 4)) isKing = true;
		while(!allPathsComplete()) iteratePath(isKing);
		if (isKing) 
		{
			ArrayList<pathNode> nextpath = new ArrayList<pathNode>();
			nextpath.add(new pathNode(t,start));
			allPaths.add(nextpath);
			while(!allPathsComplete()) iteratePath(false);
		}
		
		//make sure if there are jumps those are the only moves returned
		checkForJumps();
	}
	
	/**
	 * Iterate across all possible paths for a chip on the board.
	 */
	private void iteratePath(boolean isKing)
	{
		pathNode node;
		ArrayList<pathNode> path;
		ArrayList<pathNode> leftPath;
		ArrayList<pathNode> rightPath;
		ArrayList<pathNode> newPath;
		
		for (int p=0; p<allPaths.size();p++)
		{
			//get the current path
			path = (ArrayList<pathNode>) allPaths.get(p);
		
			//is the path complete?  If so, evaluate the next one.
			node = path.get(path.size()-1);
			if (node.action == end) continue;
			if (!isKing)
			{
			//can I go left?
			leftPath = goLeft(node,false);
			 
			//can I go right?
			rightPath = goRight(node,false);
			
			//if there was a left or right path generated, 
			// add them to path
			if ((leftPath.size() > 0) && (rightPath.size() > 0))
			{
				newPath = (ArrayList<pathNode>) path.clone();
				path.addAll(leftPath);
				newPath.addAll(rightPath);
				allPaths.add(newPath);
			}
			else if (leftPath.size() > 0)
			{
				path.addAll(leftPath);
			}
			else if (rightPath.size() > 0)
			{
				path.addAll(rightPath);
			}
			else 
			{
				path.add(new pathNode(node.tile,end));
			}
			}
			if (isKing)
			{
				//can I go left?
				leftPath = goLeft(node,true);
				 
				//can I go right?
				rightPath = goRight(node,true);
				
				//if there was a left or right path generated, 
				// add them to path
				if ((leftPath.size() > 0) && (rightPath.size() > 0))
				{
					newPath = (ArrayList<pathNode>) path.clone();
					path.addAll(leftPath);
					newPath.addAll(rightPath);
					allPaths.add(newPath);
				}
				else if (leftPath.size() > 0)
				{
					path.addAll(leftPath);
				}
				else if (rightPath.size() > 0)
				{
					path.addAll(rightPath);
				}
				else 
				{
					path.add(new pathNode(node.tile,end));
				}
			}
		}
	}
	
	/** 
	 * Move to the left
	 * @param path
	 * @return
	 */
	private ArrayList<pathNode> goLeft(pathNode node,boolean isKing)
	{
		ArrayList<pathNode> newPath = new ArrayList<pathNode>(0);
		
		//if the node is already an endpoint, then return
		if (node.action == end) return newPath;
		
		int [] forward = board.goForward(node.tile, player); //manager.currentPlayer());
		if (isKing) forward = board.goBackward(node.tile, player); //manager.currentPlayer());
		
		if (forward[0] == -1) return newPath;
		
		//check to see if there is a chip on the tile
		//chip aChip = manager.chipOnTile(forward[0]);
		//if (aChip == null )
		if (boardArray[forward[0]] == 0)
		{
			if (node.action != start) return newPath;
			//move to the tile
			newPath.add(new pathNode(forward[0],cell));
			newPath.add(new pathNode(forward[0],end));
			return newPath;
		}
		
		//is the chip one of yours?
		//if (aChip.player() == manager.currentPlayer())
		if (((player == manager.player1) && (boardArray[forward[0]] < 0))
			|| ((player == manager.player2) && (boardArray[forward[0]] > 0)))
		{
			newPath.add(new pathNode(node.tile,end));
			return newPath;
		}
		//if not, check if there is a chip on the next tile
		int [] jumpForward = board.goForward(forward[0], player);
		if (isKing) jumpForward = board.goBackward(forward[0], player);
		//chip anotherChip = manager.chipOnTile(jumpForward[0]);
		//if ((jumpForward[0] == -1) || (anotherChip != null))
		if ((jumpForward[0] == -1) || (boardArray[jumpForward[0]] != 0))
		{
			return newPath;
		}
		//if not, jump the chip and go to the tile.
		newPath.add(new pathNode(forward[0],jumpLeft));
		newPath.add(new pathNode(jumpForward[0],cell));
		
		return newPath;
	}
	
	/**
	 * Move to the right
	 * @param path
	 * @return
	 */
	private ArrayList<pathNode> goRight(pathNode node, boolean isKing)
	{
		ArrayList<pathNode> newPath = new ArrayList<pathNode>(0);
		
		//if the node is already an endpoint, then return
		if (node.action == end) return newPath;
		
		int [] forward = board.goForward(node.tile, player);
		if (isKing) forward = board.goBackward(node.tile, player);
		
		// there is no tile to my right
		if (forward[1] == -1)  return newPath;
		
		//check to see if there is a chip on the tile
		//chip aChip = manager.chipOnTile(forward[1]);
		//if (aChip == null)
		if (boardArray[forward[1]] == 0)
		{
			if (node.action != start) return newPath;
			//move to the tile
			newPath.add(new pathNode(forward[1],cell));
			newPath.add(new pathNode(forward[1],end));
			return newPath;
		}
		
		//is the chip one of yours?
		//if (aChip.player() == manager.currentPlayer())
		if (((player == manager.player1) && (boardArray[forward[1]] < 0))
			|| ((player == manager.player2) && (boardArray[forward[1]] > 0)))
		{
			newPath.add(new pathNode(node.tile,end));
			return newPath;
		}
		//if not, check if there is a chip on the next tile
		int [] jumpForward = board.goForward(forward[1], player);
		if (isKing) jumpForward = board.goBackward(forward[1], player);
		
		//chip anotherChip = manager.chipOnTile(jumpForward[1]);
		//if ((jumpForward[1] == -1) || (anotherChip != null))
		if ((jumpForward[1] == -1) || (boardArray[jumpForward[1]] != 0))
		{
			return newPath;
		}
		//if not, jump the chip and go to the tile.
		newPath.add(new pathNode(forward[1],jumpRight));
		newPath.add(new pathNode(jumpForward[1],cell));
		
		return newPath;
	}
	
	/**
	 * Check that all paths have been completed.
	 * @return
	 */
	private boolean allPathsComplete()
	{
		ArrayList<pathNode> path;
		pathNode node;
		
		for (int p=0; p < allPaths.size(); p++)
		{
			path = (ArrayList<pathNode>) allPaths.get(p);
			node = path.get(path.size()-1);
			if (node.action != end) return false;
		}
		
		return true;
	}
	
	public ArrayList<ArrayList<pathNode>> getAllPaths()
	{
		return allPaths;
	}
	
	private void checkForJumps()
	{
		ArrayList<pathNode> path;
		pathNode node;
		int [] jumps = new int [allPaths.size()];
		 int total = 0;
		 
		//check for jumps - 
		 for (int p=0; p < allPaths.size();p++)
		 {
			 path = (ArrayList<pathNode>) allPaths.get(p);
			 for (int n=1;n < path.size()-1;n++)
			 {
				 node = path.get(n);
				 if ((node.action == chipPath.jumpLeft) || (node.action == chipPath.jumpRight)) jumps[p] += 1;
			 }
			 total += jumps[p];
		 }
		 
		 //if there are jumps, those should be the only valid moves
		 if (total > 0)
		 {
			 ArrayList<pathNode>[] list = new ArrayList[allPaths.size()];
			 list = allPaths.toArray(list);
			 allPaths.clear();
			 for (int j=0; j < jumps.length; j++)
			 {
				 if (jumps[j] > 0)
				 {
					 allPaths.add(list[j]);
				 }
			 }
		 }
		 allPaths.trimToSize();
	}
	
	public static ArrayList<ArrayList<pathNode>> findAllPaths(byte player, int [] a, checkersBoard b, chipManager c)
	{
		ArrayList<ArrayList<pathNode>> validPaths = new ArrayList<ArrayList<pathNode>>(0);
		ArrayList<ArrayList<pathNode>> paths;
		ArrayList<pathNode> aPath;
		pathNode node;
		chipPath chippath;
		
		for (int t=0; t<32; t++)
		{
			chippath = null;
			if ((player > 0) && (a[t] > 0)) chippath = new chipPath(t,a,b,c);
			if ((player < 0) && (a[t] < 0)) chippath = new chipPath(t,a,b,c);
			if (chippath != null)
			{
				paths = chippath.getAllPaths(); 
				for (int p=0; p < paths.size();p++)
				{
					 aPath = (ArrayList<pathNode>) paths.get(p);
					 if (aPath.size() < 3) continue; 
					 validPaths.add(aPath);
				 }
			}
		}
		
		//check for jumps - 
		 int [] jumps = new int [validPaths.size()];
		 int total = 0;
		 for (int v=0; v < validPaths.size();v++)
		 {
			 aPath = (ArrayList<pathNode>) validPaths.get(v);
			 for (int n=1;n < aPath.size()-1;n++)
			 {
				 node = aPath.get(n);
				 if ((node.action == chipPath.jumpLeft) || (node.action == chipPath.jumpRight)) jumps[v] += 1;
			 }
			 total += jumps[v];
		 }
		 
		 //if there are jumps, those should be the only valid moves
		 if (total > 0)
		 {
			 ArrayList<pathNode>[] list = new ArrayList[validPaths.size()];
			 list = validPaths.toArray(list);
			 validPaths.clear();
			 for (int j=0; j < jumps.length; j++)
			 {
				 if (jumps[j] > 0)
				 {
					 validPaths.add(list[j]);
				 }
			 }
		 }
		 validPaths.trimToSize();
		
		return validPaths;
	}
}
